\documentclass{article}

\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
% \usepackage[T1]{fontenc}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage[final]{pdfpages}
\usepackage{tikz}

\date{\vspace{1 cm} \today}
\author{\vspace{2 cm} \\
  Groupe :\\
  \vspace{0.1 cm}\\
  MANGIN Adrien\\
  SARTHOU Valentin\\
\vspace{1 cm}\\
Responsable :\\
\vspace{0.1 cm}\\
BARTHOU Denis}
\title{Projet de Compilation\\Compilateur pour le langage Ruby\\-\\Rapport}


\usepackage{fancyhdr}
\lhead{Projet de compilation - Semestre 7 - Compilateur pour le langage Ruby }
\rhead{}
\renewcommand{\headrulewidth}{1px}
\lfoot{ \bsc{Enseirb-Matmeca 2012-2013}}
\rfoot{ \bsc{Filière Informatique - I2}}
\renewcommand{\footrulewidth}{1px}
\pagestyle{fancy}


\begin{document}

\thispagestyle{empty}
\begin{figure}
  \includegraphics[width=0.25\textwidth]{Logo_ENSEIRB-MATMECA.png}
\end{figure}
\maketitle

\newpage

\section{Introduction}

Le projet consiste à réaliser un compilateur proche du langage Ruby, qui sera ensuite compilé à l'aide de LLVM. Il s'agit de compléter le fichier parse.y fourni dans l'énoncé afin qu'il réponde aux différentes opérations demandées, et qu'il génère du code LLVM fonctionnel sans causer de troubles à la compilation ou à l'exécution.

\section{Implémentation des données de base}

Dans un premier temps, nous avons traité les opérations de base du fichier parse.y. Pour ce faire, nous avons mis au point différentes sructures nous permettant de stocker les données que nous aurions à utiliser.
\subsection{Structures mises en place}

Au cours de ce projet, nous avons mis en place quatre structures de données afin de stocker nos variables.
\\
\begin{itemize}
  \item
    La structure \textbf{var} est une structure chaînée nous permettant de représenter une variable. Elle est composée de plusieurs champs :
\\
    \begin{itemize}
      \item
        Le champ \textbf{nom} représente le nom de la variable tel qu'il est donné dans les fichiers à analyser par le compilateur.
      \\
      \item
        Le champ \textbf{r} sert à stocker le numéro de registre dans lequel est stocké la variable. Cela est notamment nécessaire lorsque le compilateur doit afficher une opération donnée, afin qu'il trouve les variables sur lesquelles il doit agir et puisse stocker le résultat dans un registre encore vierge, afin d'éviter de générer des erreurs dues à l'utilisation multiple d'un même registre.
      \\
      \item
        Le champ \textbf{u} est une union contenant un int, un float et une chaîne de caractères. Selon le type de la variable, un seul de ces trois champs est rempli et représente sa valeur (lorsque celle-ci est calculable).
      \\
      \item
        Le champ \textbf{type} est un int permettant de représenter le type de la variable. On dispose de six types différents représentables : int, float, string, booléen, fonction et void.
      \\
      \item
        Le champ \textbf{prec} est une structure var pointant vers l'élément précédent dans la pile. Ce champ s'avère pratique lorsqu'il s'agit de dépiler à la fin d'un bloc de code ou lors de la libération à la fin du programme.
      \\
      \item
        Le champ \textbf{calculable} est un booléen, permettant de connaître la calculabilité d'une variable. Cette valeur nous permet de pouvoir précalculer, lorsque c'est possible, la valeur d'une variable. Par exemple, il est inutile de calculer à l'exécution du programme la valeur de 1+1.
      \\
      \item
        Enfin, Le champ \textbf{code} est une chaîne de caractères contenant le code LLVM correspondant aux calculs effectués pour cette variable.
      
    \end{itemize}

~
  
  \item
    La structure \textbf{sdc} (pour structure de contrôle) est une structure chaînée nous permettant notamment de représenter le code associé à une structure de contrôle telle que \textit{if}, \textit{for} ou \textit{while}. Elle dispose, tout comme \textbf{var}, d'un champ \textbf{code} et d'un champ \textbf{prec}, mais possède en plus un champ \textbf{int\_else}, qui définit, dans le cas où on tombe sur une boucle \textit{if...then}, s'il y a un \textit{else} ou pas.
  \\
  
  \item
    La structure \textbf{exprs} permet, quant à elle, de stocker les paramètres d'une fonction, et ainsi de vérifier si le nombre de paramètre lors d'un appel est correct. Elle est composée de deux champs : Le champ \textbf{vars} est un tableau de structures \textbf{var} et est chargé de stocker les différents paramètres. Le deuxième champ, \textbf{nb}, stocke leur nombre.
  \\
  
  \item
    Enfin, la structure \textbf{table} permet de stocker les variables, qu'elles soient locales ou globales, dans trois piles différents. Une quatrième pile, quant à elle, permet de stocker les structures \textbf{sdc}. 
  
\end{itemize}

\subsection{Les opérations mathématiques}

Une fois nos structures en place, nous nous sommes intéressés aux opérations mathématiques. Néanmoins, avant cela, il nous a fallu choisir la méthode que nous mettrions en place afin d'analyser les fichiers à compiler. Nous avons décidé d'utiliser \textit{yyparse()} une unique fois et donc de n'effectuer qu'une seule passe.

~

En ce qui concerne le typage des données, tous les entiers et les variables de type entier sont représentées en LLVM par le type i32, ceci indépendamment d'un éventuel overflow (Les opérations sur les entiers sont effectuées modulo $2^{32}$). De même, les flottants sont représentés par le type LLVM float. Les variables stockant le résultat d'une opération telle que \textit{icmp} ou \textit{fcmp} sont représentées par le type LLVM i1 (booléen).

~

En ce qui concerne les opérations mathématiques, nous avons mis en place une fonction, \textbf{expr}, qui permet de générer le code associé à une expression donnée. Cette fonction prend notamment en paramètre les deux variables sur lesquelles l'opération est effectuée, l'opcode de l'opération pour les entiers et pour les flottants, le résultat de l'opération lorsque les variables sont calculables, ainsi que le registre dans lequel stocker le résultat.

~

Dans un premier temps, \textbf{expr} vérifie que les deux variables passées en paramètre sont du même type. Dans le cas contraire, il retourne une erreur, le compilateur LLVM ne gérant pas ce cas de figure.
Ensuite, la fonction \textbf{expr} vérifie la calculabilité des deux variables. Le cas échéant, elle crée une variable entière ou flottante, selon le type des variables à opérer, qui sera donc par la suite non calculable. \\
Dans le cas contraire, selon le type de la première variable (et donc de la deuxième), elle crée une variable de valeur nulle (flottante ou entière) et elle doit gérer l'affichage du code associé à chacune des deux variables.\\
Dans le cas des opérations de comparaison, le type de retour est un booléen, on doit donc le préciser à la variable de retour.

\subsection{AND et OR}

Tout d'abord, on vérifie que les variables sont entières, LLVM ne gérant pas AND et OR pour des flottants. Ces deux opérations sont gérées de la même manière que les précédentes.

\section{Implémentation des structures de contrôle}

Dans l'implémentation du compilateur, nous avons considéré que des variables définies à l'intérieur d'un bloc if, for ou while n'étaient pas accessibles dans des blocs de niveau supérieur ou égal. Il a donc fallu mettre en place un système de pile, en empilant une à une les variables lorsque'elle sont définies, et en les dépilant à la fin d'un bloc.

\noindent Pour cela, nous avons défini une variable spéciale jouant le rôle de sentinelle. Lorsque le parseur lit le mot-clé IF, FOR ou WHILE, il empile une sentinelle sur la pile des variables locales, et à la fin de la structure de contrôle (au niveau du \textit{end} en Ruby), il dépile les variables jusqu'à trouver une sentinelle.

\noindent Pour chacune des structures conditionnelles, il s'agit d'effectuer un ou plusieurs branchements conditionnels. Pour la boucle for, il faut également prévoir une incrémentation (et éventuellement une allocation) pour la variable de boucle.

\subsection{Détail sur la structure If}

La grammaire définie dans le fichier \textit{parse.y} ne permettait pas d'effectuer des actions avant la fin du traitement de la structure (ambiguïté). Nous avons donc modifié la grammaire en fusionant les deux règles IF, la condition ELSE devenant optionnelle.

\noindent Cela nous a permis de pouvoir dépiler les éventuelles variables définies dans le premier bloc de code ``then ...'' pour pouvoir générer du code correct au niveau du bloc ``else ...''


\section{Limites du compilateur}

Notre compilateur ne prend en compte ni les chaînes de caractères ni la déclaration de fonctions ou de classes. Les appels de fonctions sont limités aux deux fonctions \textit{print\_i()} et \textit{print\_f()} qui nous permettent d'afficher respectivement les entiers et les flottants.


\end{document}
